package SLR;

import javax.swing.text.html.HTMLDocument;
import java.util.*;


public class SLR {
    //主程序接受文法
    //处理字符，处理first集和follow集 ， 输出DFA *，预测分析表，接受过程
    List<String> G0 =new ArrayList<String>() ;
    HashMap<String, HashSet<String>> First1=new HashMap();
    Map G1 =new HashMap< String , ArrayList<String> >();
    Set all =new HashSet() ;
    Set endChar =new HashSet();
    Set unendChar =new HashSet();
    ArrayList<Item> Items ;
//    First first =new First();
//    Follow follow ;
    public SLR(List<String> G){
        //初始化所接收的增广文法
        G0=G;
        //分离终结符和非终结符
        Set leftchar =new HashSet<String>();
        Set rightchar =new HashSet<String>();
        for (int i = 0; i <G.size() ; i++) {
            String line=G.get(i);
            String[] k=line.split("->");
            //将数组转成map,注意点在于，我们可能会遇到 F-》k，F-》f这样的话，我们就要更新map的value集
            HashSet<String> kk =new HashSet<String>();
            if(G1.containsKey(k[0]) )
            {
                //如果包含这个非终结符 说明已经有一个支付串在里面了，于是我们就是要更新这个字符集
                kk =(HashSet<String>)G1.get(k[0]);
                kk.add(k[1]);
                G1.put(k[0],kk);
            }
            else{
                //不包含终结符就是没初始化过
                kk.add(k[1]);
                G1.put(k[0],kk);
            }
            //处理终结符和非终结符
            leftchar.add(k[0]);

            for (int j = 0; j <k[1].length() ; j++) {
                rightchar.add(""+k[1].charAt(j));
            }
        }
        //左边就是非终结符，右边去掉左边就是非终结符
             unendChar=leftchar;
            Iterator<String> itr = rightchar.iterator();
            while(itr.hasNext()){
                String k =itr.next();
                if(!unendChar.contains(k)) endChar.add(k);
            }
        System.out.println("非终结符"+unendChar);
        System.out.println("终结符"+endChar);

        //初始化
//        System.out.println("First : " + first.k);
        System.out.println("G1:" + G1);

//        System.out.println(getItem("B->。aB", 1));
        Items=getItems2();
        System.out.println("Item :"+getItems2());
        System.out.println("Map :"+DFAmap);
//        System.out.println(togetFirst("T"));
        G1.remove("S'");

        for (Object key :G1.keySet() ) {
            First.put((String)key,new HashSet<String>());
            Follow.put((String)key,new HashSet<String>() );
        }
        System.out.println();
        bulitFirst();
        System.out.println("First  :"+First);
        builtFollow();
        System.out.println("Follow :"+Follow);
        visualization();
        bulitAnalysistable();
        printtable();

    }

    HashMap<Integer,HashMap<String,HashSet<Integer>>> secondMap =new HashMap<Integer,HashMap<String,HashSet<Integer>>>();







    public void visualization(){
        //将族群和图整合一起生成直观图
        ArrayList<Item> Items =getItems2();
        for (int i = 0; i < Items.size(); i++) {
            ArrayList<String> item =Items.get(i).getItem();
            int index =Items.get(i).getIndex();
            System.out.println("I"+index);
            for (int j = 0; j <item.size() ; j++) {
                System.out.println(item.get(j));
            }
//            输出单向图

            if(!DFAmap.keySet().contains(index)) continue;
            HashSet map =DFAmap.get(index);

            Iterator ii = map.iterator();

            while(ii.hasNext())
            {
                HashMap<Integer,String> oo= (HashMap<Integer, String>) ii.next();
                for (Object key :oo.keySet())
                {
                    if (((String)oo.get(key)).equals("NULL")) ;
                    else
                    System.out.println("I"+index+" 遇到"+oo.get(key)+" 转换到 I"+key);

                }

            }
            System.out.println("//////////////////////////");
            System.out.println("//////////////////////////");
            System.out.println("//////////////////////////");

        }
    }
    public ArrayList<Item> getItems2()
    {
        ArrayList<Item> items =new ArrayList<Item>();
        HashMap<Integer,ArrayList<String>> set =new HashMap<Integer,ArrayList<String>>();
        String start =G0.get(0);
        Item stratitem =getItem(start,0);
        items.add(stratitem);
        set.put(0,stratitem.getItem());
        set.put(1,new ArrayList<>());
        int kkk=2;
        for (int i = 0; i <items.size() ; i++) {
            Item nowitem = items.get(i);//处理这个集合
            ArrayList<String> list = nowitem.getItem();//所有话
//            System.out.println(list);
            HashSet<String> dealed = new HashSet<>();
            HashSet<String> group = new HashSet<>();
            for (int j = 0; j <list.size() ; j++) {
                //一个一个遍历
                    String str = list.get(j);
                if(dealed.contains(str)) continue;
                else {
                    group.add(str);
                    for (int k = j + 1; k < list.size(); k++) {
                        String word = gettheword(list.get(k));
                        if (gettheword(str).equals(word)) {
                            group.add(list.get(k));
                        }

                    }
                    //这里处理这一组的事务

                    Item item =new Item(items.size());

                    HashSet<String> keke =new HashSet<>();
                    for (String strrr : group){
                        if(!(strrr.charAt(strrr.length()-1)+"").equals("。"))
                        {Item NewItem =getItem(strrr,0);
                        keke.addAll(NewItem.getItem());
//                        System.out.println(strrr);
                        }
                    }
                    ArrayList<String> ok =new ArrayList<>(keke);
                    if(!set.containsValue(ok)) {
                        item.setItem(ok);
                        items.add(item);
                        set.put(kkk, ok);
                        kkk++;
                        maprecord(str,i,item.getIndex());
                    }
                    else{
                        for (int k = 0; k <items.size() ; k++) {
                            if(items.get(k).getItem().equals(ok))
                                maprecord(str,i,items.get(k).getIndex());
                        }
                        if(str.charAt(str.length()-1)=='。') maprecord(str,i,i);
                    }
//                    System.out.println(group);
                    dealed.addAll(group);
                    group.clear();
                }

            }
        }
        return items;
    }
    public String gettheword(String G){
        String [] kk =G.split("。");
        if(kk.length==1) return "";
        else return kk[1].charAt(0)+"";
    }


    HashMap<Integer,HashSet<HashMap<Integer,String>>> DFAmap =new HashMap<Integer,HashSet<HashMap<Integer,String>>> ();


    public void maprecord(String str,int fromindex ,int toindex) {
            if(str.charAt(str.length()-1)=='。')
            {
                HashMap<Integer,String> oo  = new HashMap<Integer, String>();
                oo.put(fromindex,"NULL");
                HashSet ooo=new HashSet();
                ooo.add(oo);
                if (DFAmap.keySet().contains(fromindex))
                    DFAmap.get(fromindex).add(oo);
                else
                    DFAmap.put(fromindex,ooo);
            }
            else{
                String [] Block =str.split("。");
                String word =Block[1].charAt(0)+"";
                HashMap<Integer,String> oo  = new HashMap<Integer, String>();
                oo.put(toindex,word);
                HashSet ooo=new HashSet();
                ooo.add(oo);
                if (DFAmap.keySet().contains(fromindex))
                DFAmap.get(fromindex).add(oo);
                else
                    DFAmap.put(fromindex,ooo);
            }
    }

    //输入：指定文法串 GG ，用户所输入的文法G  ，
    //输出：GG所衍生出来的项目集
    //思路：先识别。的位置 例如S->。BB,
    // 生成S->B。B(移动识别符)
    // 、然后找出从文法G 中 找出 B的生成式B->aB
    // 并在第一个字符a前添加。号

    // 移动。的情况1.文法串中没有。，就生成。在右部第一个字符头
    // 2.有。向右一位移动。号
    // 3.。在最右边，不移动.

    public Item getItem(String GG,int index){
            Item item =new Item(index);
            String line =rightShift(GG);//移位后的文法串
            //判断一下是移入项目还是规约项目
            if (line.charAt(line.length()-1)=='。'){//规约项目直接加line就好
                 item.addG(line);
            }
            else{
            //移入项目就识别第一个字符
            String[] Block =line.split("。");
            String char_0 =Block[1].charAt(0)+"";
            // 如果是终结符也不需要处理line
            if(endChar.contains(char_0)){
                item.addG(line);
            }
            else{//如果是非终结符就     查给定文法 G1的所有衍生子集 给其右部首加上。然后添加到  item中
                HashMap<String,Boolean> this_dealed =new HashMap<String,Boolean>();
                item.addG(line);
                this_dealed.put(char_0,false);
                Boolean flag= true;
                while(flag)
                {
                    ArrayList<String> lines=new ArrayList<String>((Set) G1.get(char_0));
                    for (int i = 0; i <lines.size() ; i++) {
                        String l =char_0+"->"+lines.get(i);
                        //如果在这里遇到了首字母是非终结符的，且未被处理过的
                        //就添加到this_dealed
                        String ok= ""+lines.get(i).charAt(0);
                        if(unendChar.contains(ok) && !this_dealed.keySet().contains(ok)){
                            this_dealed.put(ok,false);
                        }
                        String k= rightShift(l);
                        item.addG(rightShift(l));
                    }
                    this_dealed.put(char_0,true);
                    if(!this_dealed.containsValue(false)) flag=false;
                    else {
                        //找到一个没处理过的终结符继续处理
                        // 即 将char_0置为这个没处理过的非终结符.
                        for (String key :this_dealed.keySet()){
                            if(!this_dealed.get(key)){
                                char_0=key;
                            }
                        }
                    }
                }
            }
        }
        return item;
    }

    // 移动。的情况1.文法串中没有。，就生成。在右部第一个字符头 例子 S->。SS
    // 2.有。向右一位移动。号 例子S->S。S
    // 3.。在最右边，不移动. 例子：S->SS。
    public String rightShift(String GG)
    {
        String newGG =new String();
        if(!GG.contains("。"))
        {
            String[] Block =GG.split("->");
            newGG=Block[0]+"->。"+Block[1];
        }
        else if (GG.charAt(GG.length()-1)=='。'){//在最右边，是规约项目
            newGG =GG;
        }
        else {
            String[] Block =GG.split("。");
            String i =""+Block[1].charAt(0);
            newGG=Block[0]+i+"。"+Block[1].substring(1);
        }

        return newGG;
    }



//    first集求法，1，找每个产生式第一个字母，2如果这个字母是终结符，我们直接加入first集中。
//    3如果这个字母是非终结符，首先加入该非终结符的First集，
//     然后观察是否有空集，如果有空集就要回到第一个式子的第二个终结符进行同样操作，直到出现空串或者终结符
 Map<String,HashSet<String>> First = new HashMap<String,HashSet<String>>();
    public void bulitFirst(){
        boolean change =true;

        while(change)
        {
            change=false;
            int size_0 =0;
            for (Object left : G1.keySet()) {
                  ArrayList<String>  right =new ArrayList<String> ((HashSet)G1.get(left));
                  size_0= First.get((String) left).size();
                for (int i = 0; i <right.size() ; i++) {
                        int point=0;
                        String word  =right.get(i).charAt(point)+"";
                        if(endChar.contains(word)){
                            First.get(left).add(word);
                            if(First.get(left).size()>size_0) change=true;
                        }
                        else if(unendChar.contains(word)){
                            Set<String> kk ;
                            do {
                                if (point==right.get(i).length()){
                                    First.get(left).add("∅");
                                    break;
                                }
                                word =right.get(i).charAt(point)+"";
                                kk=First.get(word);

                                Iterator<String> it = kk.iterator();
                                while (it.hasNext()) {
                                    String tempc = (String) it.next();

                                    if (!tempc.equals("∅")) {
                                        First.get(left).add(tempc);
                                    }
                                }
                                ++point;
                            }while (kk.contains("∅"));
                            if (First.get(left).size()>size_0)
                                change=true;
                        }
                }
            }
        }
    }

    //输入：First集，文法集G，
    //输出：follow集
//     求法： 首先给follow（s‘）中的终结符添加$
//     然后搞右部的 第一个非终结符K 找到这个终结符后面是1，终结符 ，2 终结符，3，没有符号，K为最后一个字符
//     如果k为最后一个字符，则该follow(K)=follow(S') ，
//     如果是终结符，就将这个终结符添加到follow（K）中
//     如果是非终结符O，在K的follow集中添加O的first集
//    如果first（o）中包含 空串  我们就可以返回这个式子，找到o后面的字符 L 并重复上面的判断，
//     直到这个式子结束
//    并且这个follow集在计算完成之前是一直在迭代的，
//     例如follow(K)=follow(S') 若follow（S’）变化，follow（K）也要变化，但反过来不成立
    Map<String,HashSet<String>> Follow = new HashMap<String,HashSet<String>>();
    public void builtFollow(){
        String start_word =G0.get(0).charAt(4)+"";
        Follow.get(start_word).add("$");
        Boolean change =true;
        while (change)
        {
            change=false;
            int size_0=0;
            for (Object left : G1.keySet()) {
                ArrayList<String>  right =new ArrayList<String> ((HashSet)G1.get(left));
                for (int i = 0; i <right.size() ; i++) {
                    int point =0;
                    while(point<right.get(i).length())
                    {
                        String firstword =""+right.get(i).charAt(point);
                        if(endChar.contains(firstword)){
                            point++;
                            continue;
                        }
                        if(right.get(i).length()>point+1){
                            String secondword =right.get(i).charAt(point+1)+"";
                            size_0=Follow.get(firstword).size();
                            if(endChar.contains(secondword))
                            {
                                Follow.get(firstword).add(secondword);
                                if(Follow.get(firstword).size()>size_0) change=true;
                            }
                            else  if(unendChar.contains(secondword))
                            {
                                Iterator<String> it = First.get(secondword).iterator();
                                while (it.hasNext()) {
                                    String tempc = (String) it.next();
                                    if (!tempc.equals("∅")) {
                                        Follow.get(firstword).add(tempc);
                                    }
                                }

                                if(Follow.get(firstword).size()>size_0) change=true;
                                //  如果该终结符在
                                if(First.get(secondword).contains("∅")) {

                                    Follow.get(firstword).addAll(Follow.get(left));
                                    if(Follow.get(firstword).size()>size_0)
                                        change = true;
                                }

                            }

                        }else if(right.get(i).length()==point+1)
                        {
                            if(unendChar.contains(firstword)){
                                size_0=Follow.get(firstword).size();
                                Follow.get(firstword).addAll(Follow.get(left));
                                if(Follow.get(firstword).size()>size_0)
                                    change = true;
                            }
                        }
                        point++;
                    }

                }
                    }
                }

        }

        HashMap<Integer,ArrayList<String>> table =new HashMap<>();
        HashMap top =new HashMap();
        public void bulitAnalysistable()
        {
            //初始化表

            int ii=0;
            for (Object key :endChar){
                top.put((String)key,ii);
                ii++;
            }
            top.put("$",ii);
            for (Object key :unendChar){
                top.put((String)key,ii);
                ii++;
            }
            for (int i = 0; i <Items.size() ; i++) {
                ArrayList<String> row =new ArrayList<>();
                for (int j = 0; j < top.size() ; j++) {
                    row.add(new String());
                }
                table.put(i,row);
            }
            //转换DNFmap
            for (int key :DFAmap.keySet()) {//key是族的序号
                for (HashMap<Integer, String> map : DFAmap.get(key)) {
                    for (int keykey : map.keySet()) {//这个不是一层循环只是为了简便取出这个map的键对值
                        // map中值是NULL的即为规约项目
                        // ，如果这个规约项目族序号（key）是1，在 $ 对应序号（在top中找）下 写入acc
                        // 如果是普通规约项目就要先找对应的规约的范式的序号，并在这个下面全写入r +范式序号
                        String value =map.get(keykey);
                        if(value.equals("NULL")){
                                if(key==1) {
                                        int $index ;
                                        $index=(int)top.get("$");
                                        table.get(1).set($index,"acc");
                                }
                                else{
                                    //找到这个范式的序号
                                    int Rindex=-1;
                                    ArrayList<String> ok =Items.get(key).getItem();
                                    String thestr=new String();
                                    if(ok.size()==1){
                                        String str = ok.get(0).substring(0,ok.get(0).length()-1);
                                        thestr=str;
                                    }
                                    else {
                                        for (int i = 0; i <ok.size() ; i++) {
                                            String words =ok.get(i);
                                            if((words.charAt(words.length()-1)+"").equals("。")){
                                                thestr =words.substring(0,words.length()-1);
                                            }
                                        }
                                    }
//                                    System.out.println("thestr :" +thestr);
                                    for (int i = 0; i <G0.size() ; i++) {
                                        String ooo =G0.get(i);
                                        if(ooo.equals(thestr))
                                            Rindex =i;
                                    }
//                                    System.out.println(Rindex);
                                    for (int i = 0; i <top.size() ; i++) {
                                        table.get(key).set(i,"r-"+Rindex);

                                    }
//                                    System.out.println("ok:"+ok);
                                }
                        }



                    }
                }
            }
            for (int key :DFAmap.keySet()) {//key是族的序号
                for (HashMap<Integer, String> map : DFAmap.get(key)) {
                    for (int keykey : map.keySet()) {//这个不是一层循环只是为了简便取出这个map的键对值

                        //上面把规约项目全处理了
                        // 这边处理移入项目 就可能产生规约移入冲突
                        //所以要先检查 对应序号中有没有值
//                、如果没有值，那么在对应序号 直接填入 S +keykey
//                如果有就要查Follow集，问这个value值在这个规约项目左边的Follow集中吗
                        ArrayList<String> t =table.get(key);
                        String now =map.get(keykey);
                        if(!now.equals("NULL"))
                        {
//                            System.out.print(now+ " ");
//                            System.out.print(top.get(now)+"");
                            int nowindex =(int)top.get(now);
//                            System.out.print("  ");
                            if(t.get(nowindex).equals(new String())){
                                if(endChar.contains(now))
                                table.get(key).set( nowindex,"s-" +keykey);
                                else {
                                    table.get(key).set(nowindex,keykey+"");
                                }
                            }
                            else {//移入-规约冲突
                                //如果这个规约项目的follow集包含now 则规约，否则移进
                                String ko =table.get(key).get(keykey);
//                                System.out.println(ko);
                                String []  kko= ko.split("-");
                                int jojo =Integer.parseInt(kko[1]);
//                                System.out.println(jojo);
                                String GGGG = G0.get(jojo);
//                                System.out.println(GGGG);
                                String left =GGGG.charAt(0)+"";
//                                System.out.println(left);
                                if(!Follow.get(left).contains(now))
                                {
                                    table.get(key).set(nowindex,"s-"+keykey);
                                }

                            }
                        }
                    }
                }
            }
            System.out.println(top);
            System.out.println(table);
            System.out.println(DFAmap);
        }
        public void printtable()
        {
            System.out.print("状态\t");
            for (int i = 0; i <top.size() ; i++) {
                for (Object key :top.keySet()) {
                    if((int)top.get(key)==i) System.out.print(key +"\t");
                }
            }
            System.out.println();
            for (int i = 0; i <table.size() ; i++) {
                ArrayList<String> ii =table.get(i);
                System.out.print(i+"\t");
                for (int j = 0; j <ii.size() ; j++) {
                    System.out.print(ii.get(j)+"\t");
                }
                System.out.println();
            }
        }
}










